Modern society is increasingly dependent on the ability to communicate information. More and more applications require communications of varying quantities of information between users. The trend in communications technology is to develop packet or cell based systems for communications transport and switching at ever higher speeds.
Increasing demands for many communication services, having different requirements, drove the development of separate networks. For example, analog voice telephone services utilize a complex network of voice traffic switches, lines and trunks to provide ubiquitous switched voice connectivity virtually throughout the world. The modern telephone network carries most voice traffic in digitized form, typically using time division multiplexing techniques. The switched voice network can carry some data traffic, using moderns or ISDN interfaces. However, the telephone network cannot readily switch higher speed data traffic, therefore a variety of separate data networks evolved. Examples of such data networks include X.25, frame relay and SMDS. The construction, operation, maintenance and upgrading of such disparate networks for different services are increasingly complex and expensive, particularly as traffic demands continue to increase.
Asynchronous transfer mode (ATM) transport, an advanced, high-speed packet switching technology, has emerged as the latest form of packet or cell based switching. ATM promises fast cell switching for wide ranges of traffic demands. ATM is intended to carry virtually any type of information that can be expressed in or converted to digital form, from voice telephone traffic, to real-time video, to high-speed file transfers, to faster than real-time video, etc. ATM based networks are eliminating the need for different networks to carry different types of traffic. In ATM, transfer is asynchronous in the sense that the recurrence of cells that contain information from any particular sender is not necessarily periodic. Each device using the ATM network submits a cell for transfer when it has a cell to send. Once aggregated and scheduled, the ATM cells ride in synchronous slots on a high-speed media, such as a SONET optical fiber.
In ATM, information is organized into cells having a fixed length and format. Each cell includes a header, primarily for identifying cells relating to the same virtual connection, and an information field or "payload". The ATM standard defines a cell size of 53 bytes or octets. The first five bytes of each cell form the header, and the remaining 48 bytes represent payload data. The header of each cell includes a field for a virtual path identifier (VPI) and a virtual circuit identifier (VCI). The VPI and VCI together identify the particular circuit or communication to which each cell relates.
Within a transport stream, the VPI and VCI identifiers serve to divide the stream into separate logical or `virtual` paths and to segregate traffic within each virtual path into logical or `virtual` circuits. An ATM transport device makes the virtual circuit connections, within one or more virtual path connections, available to transport any number of individual communications over the link. Such logical circuit connections are set up and torn down, as needed, to efficiently provide required transport capacity for independent communication sessions to and from a number of separate communication devices.
Different types of communication require different transport rates. Also, different communications require different levels of service quality, sometimes referred to as quality of service or QoS. For example, real-time video transmission requires a high constant bit rate to maintain synchronism, whereas packet data communications do not. At the network speeds now available for ATM transport, voice communication becomes a bursty data traffic service. To provide these different levels of service, an ATM link typically will support a number of different types of traffic.
The specification for ATM transport defines five traffic or service categories supported by the ATM layer of the network, most notably including constant bit rate (CBR) service, variable bit rate (VBR) service and available bit rate service. CBR service provides a constant, guaranteed bandwidth over an assigned virtual circuit. VBR provides some maximum number of transmit opportunities, which may or may not be used to transmit cells over the associated virtual circuit, for example for bursty traffic. Over time, the actual rate or bandwidth may vary from almost zero (little or no use of the opportunities to send) up to the amount provided by the maximum number of transmit opportunities (full use) allocated for the circuit. With ABR service, a data communication device may have an opportunity to transmit in time slots that are available because the time slots were not used by CBR or VBR services.
For ABR service, the specification for ATM defines an allowed cell rate (ACR) and a minimum cell rate (MCR). The allowed cell rate is the bandwidth, in terms of cells per second, currently usable by a particular ABR connection. Typically, the ACR for an ABR connection varies over time, for example as a function of the traffic load on the ATM link. The minimum cell rate is the lowest bandwidth that the connection is always guaranteed.
The MCR may be zero, and if so, then the device regulating traffic need not reserve any bandwidth for the ABR connection. The scheduling device only needs to make a `best effort` to provide bandwidth, unused by other connections, for use by the ABR connection. The device can, if necessary, allocate all transmit opportunities to higher priority traffic, in which case, the ACR for the ABR circuit falls to zero.
However, if the ABR connection has an MCR value greater than zero, then the scheduling device effectively must reserve some minimum number of cell transmit opportunities for that connection, to support traffic for that connection at no less than the MCR rate. The device can not allocate all transmit opportunities to other circuits and services. In existing ATM systems, there is no scheduling mechanism available, which can dynamically schedule traffic for ABR service and guarantee non-zero minimum cell rates for the ABR connections.
An ATM segmentation and reassembly circuit sold by Digital Equipment Corporation under the name AToM3 provided a VBR service within a minimum cell rate, but not an ABR service with a minimum cell rate. The AToM3 used a static scheduling table to support constant bit rate traffic and variable bit rate traffic. The lines of the static table, indexed by cell transmit time, contained fields for high priority service and low priority service. The scheduler in the AToM3 provided a guaranteed transmit opportunity for a virtual circuit connection identified in the high priority field, to provide CBR service for that circuit. In a cell transmit time, if the scheduler identified a VCC in the high priority field for a particular time slot, a cell was transmitted for that VCC in the time slot. The scheduler used the low priority fields for variable bit rate services. In any cell transmit time when there was no high priority cell transmission scheduled, the scheduler looked to the low priority field and offered the transmit opportunity to the VCC identified in that field. A cell was transmitted for the low priority VCC if that VCC had a cell ready for transmission.
The AToM3 supported the minimum bit rate guarantee for VBR service by using identifiers for the same VBR type VCC in the high priority field and the low priority field, in different lines of the static scheduling table. When the scheduler found the VCC in the high-priority field in one line of the table, the scheduler scheduled the cell transmission for that VCC during each cell transmit time that indexed that line of the static table, just as if the scheduler were providing a CBR service. Appearances of the VCC identifier in the low priority field of a number of lines provided additional bandwidth in the form of a variable bit rate portion of the service for the particular VCC.
In this manner, the AToM3 scheduler provided CBR service, VBR service and VBR service with a guaranteed minimum cell transmission rate. ABR type service requires dynamic scheduling. Although dynamic scheduling for ABR service is separately known, the static scheduling used in the AToM3, did not support ABR service and was not readily adaptable to ABR service. As discussed earlier, the known examples of dynamic scheduling for ABR services do not support an MCR value that is greater than zero. Consequently, a need still exists for a scheduling methodology and actual ATM transport devices that can deliver ABR service with a non-zero guaranteed minimum cell rate.